// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-24 15:42
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.DeleteColumnsToMakeSorted;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class DeleteColumnsToMakeSortedUpdate {
    // 关于理解错字符串字典序导致的错误
    // 字符串字典序只需要比较靠前的字符即可
    // 获取在特定位置相同的字符串的时候可以直接使用String的compareTo方法
    String[] sameDic;
    List<String> sD = new ArrayList<>();

    public int minDeletionSize(String[] strs) {
        // 删除字符串数组中的字符使得字符串数组中的字符串是按照字典序进行排序
        // 字符串中的字符长度相等
        // 1 找出字符串数组中不符合字典序排列的字符
        // 2 可以比较两个字符串是否按照字典序进行排序
        // 3 需要变量记录相同字典序的字符串
        return findChar(strs);
    }

    // Get The Unalphabetically words
    private int findChar(String[] strs) {
        int len2 = strs[0].length();
        ArrayList<Integer> deleteIndex = new ArrayList<>();// 删除索引序列
        for (int i = 0; i < len2; i++) {
            int ans = isNoAlphabetic(strs, i);
            if (ans == 1) {
                // 当前位置字典序错误
                deleteIndex.add(i);
            } else if (ans == -1) { // 当前位置字符串序正确
                return deleteIndex.size();
            } else {
                // 存在相同字典顺序的字符串，而且顺序是正确的
                // 取出当前位置相同字典序的字符串进行比较
                sameDic = getSameWords(strs, i);
                sD.clear();
                return deleteIndex.size() + findChar(sameDic);
            }
        }
        return deleteIndex.size();
    }

    // Get The Same DictionarySort in the i Situation
    private String[] getSameWords(String[] strs, int i) {
        int L = 0;
        int R = 1;
        int length = strs[0].length();
        while (R < strs.length) {
            while (R < strs.length && strs[R].charAt(i) == strs[L].charAt(i)) {
                ++R;
            }
            while (L != R) {
                sD.add(strs[L++].substring(i + 1, length));
            }
            ++R;
            while (R < strs.length && strs[R].charAt(i) != strs[L].charAt(i)) {
                ++L;
                ++R;
            }
        }
        sameDic = new String[sD.size()];
        Iterator<String> iterator = sD.iterator();
        int num = 0;
        while (iterator.hasNext()) {
            String next = iterator.next();
            sameDic[num] = next;
            ++num;
        }

        return sameDic;
    }


    private int isNoAlphabetic(String[] strs, int i) {
        // To Predicate A String Array In A Specific Location If Is Alphabetic
        // 字典序可以是升序排序也可以是降序排序
        // 1 ->错误，0->存在相等，-1->正确
        int len = strs.length;
        for (int j = 1; j < len; j++) {
            if (strs[j - 1].charAt(i) - strs[j].charAt(i) > 0) {
                return 1;
            } else if (strs[j - 1].charAt(i) - strs[j].charAt(i) == 0) {
                return 0;
            }
        }
        return -1;
    }

}
